package com.likeycy.my.sort;

import com.likeycy.my.sort.cmp.Sort;

/**
 * @ClassName: RadixSort
 * @Description: 基数排序
 * @Author: sodagreen
 * @Date: 2021/4/3 12:44
 * @Version: 1.0
 */
public class RadixSort extends Sort<Integer> {

    @Override
    protected void sort() {
        // 先找到数组中的最大值，好确定最高位是个、十、百、千、万……中的哪一位。这样可以确定需要排多少轮
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }

        // 假设 max = 5963
        // 个位数：5963 / 1 % 10 = 3
        // 十位数：5963 / 10 % 10 = 6
        // 百位数：5963 / 100 % 10 = 9
        // 千位数：5963 / 1000 % 10 = 5
        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider);
        }

    }

    private void countingSort(int divider) {
        // 开辟内存空间，由于只对比不同位数上的0-9数字，所以长度直接为10
        int[] counts = new int[10];
        for (int i = 0; i < array.length; i++) {
            int index = array[i] / divider % 10;
            counts[index]++;
        }

        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i] + counts[i - 1];
        }

        // 从后往前遍历元素，将它放到有序数组中的合适位置
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] / divider % 10]] = array[i];
        }

        // 将有序数组赋值到array
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}
